/*
 * @lc app=leetcode.cn id=792 lang=typescript
 *
 * [792] 匹配子序列的单词数
 */

// @lc code=start
function binarysearch(target: number, idxs: number[]): number {
  let l = 0;
  let r = idxs.length - 1;
  let mid: number;
  while (l < r) {
    mid = l + Math.floor((r - l) / 2);
    if (idxs[mid] > target) {
      r = mid;
    } else {
      l = mid + 1;
    }
  }
  return idxs[l];
}

function numMatchingSubseq(s: string, words: string[]): number {
  const map = new Map<string, number[]>();
  const n = s.length;
  // 建立字符和索引的对应关系
  for (let i = 0; i < n; i++) {
    const letter = s[i];
    if (!map.has(letter)) {
      map.set(letter, []);
    }
    map.get(letter)!.push(i);
  }

  let ans = words.length;
  // 遍历words
  for (const word of words) {
    // 单词长度超过 s ，肯定不是 s 的子序列
    if (word.length > s.length) {
      ans--;
      continue;
    }
    const m = word.length;
    let p = -1;
    for (let i = 0; i < m; i++) {
      const idxs = map.get(word[i]);
      // 字符在s中不存在或者s中字符的最大索引小于当前索引,表示不是子序列
      if (!idxs || idxs[idxs.length - 1] <= p) {
        ans--;
        break;
      }
      // 在当前字符的索引数组中找到的第一个位置大于 p 的索引
      p = binarysearch(p, idxs);
    }
  }

  return ans;
}
// @lc code=end
